502. IPO
Description
Solution
Fix capital then find maximal profit by priority_queue
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| class Solution { static bool cmp(pair<int,int>a, pair<int,int>b){ return a.second < b.second; } public: int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) { priority_queue<int, vector<int>, less<>> pq; vector<pair<int,int>> projs; for(int i = 0; i < profits.size(); i++) projs.push_back({profits[i], capital[i]}); sort(projs.begin(), projs.end(), cmp); int start = 0, i; while(k--){ for(i = start; i < projs.size() && projs[i].second <= w; i++) pq.push(projs[i].first); start = i; if(pq.empty()){ return w; } w += pq.top(); pq.pop(); } return w; } };
|